using System;
using System.Text;
using SUnit.Core;

namespace TestDinamico
{
	[SUnitTest]
	public class BinarySearchTreeTests
	{
		[SUnitTestCase]
		public static void TestInsertValues()
		{
			BinarySearchTree tree = new BinarySearchTree(5);

			CValue[] parameters = new CValue[] { _getBSTValue(tree), new CInt(3) };
			CValue res = DynamicTest.InvokeFunction("addBSTNode", parameters, _getBSTType());
			tree.Insert(3);
			DynamicTest.AssertEquals(_getBSTValue(tree), res);
            Console.WriteLine(tree);

			parameters = new CValue[] { _getBSTValue(tree), new CInt(8) };
			res = DynamicTest.InvokeFunction("addBSTNode", parameters, _getBSTType());
			tree.Insert(8);
			DynamicTest.AssertEquals(_getBSTValue(tree), res);
            Console.WriteLine(tree);

			parameters = new CValue[] { _getBSTValue(tree), new CInt(2) };
			res = DynamicTest.InvokeFunction("addBSTNode", parameters, _getBSTType());
			tree.Insert(2);
			DynamicTest.AssertEquals(_getBSTValue(tree), res);
            Console.WriteLine(tree);

			parameters = new CValue[] { _getBSTValue(tree), new CInt(10) };
			res = DynamicTest.InvokeFunction("addBSTNode", parameters, _getBSTType());
			tree.Insert(10);
			DynamicTest.AssertEquals(_getBSTValue(tree), res);
            Console.WriteLine(tree);

			parameters = new CValue[] { _getBSTValue(tree), new CInt(9) };
			res = DynamicTest.InvokeFunction("addBSTNode", parameters, _getBSTType());
			tree.Insert(9);
			DynamicTest.AssertEquals(_getBSTValue(tree), res);
            Console.WriteLine(tree);

			parameters = new CValue[] { _getBSTValue(tree), new CInt(4) };
			res = DynamicTest.InvokeFunction("addBSTNode", parameters, _getBSTType());
			tree.Insert(4);
			DynamicTest.AssertEquals(_getBSTValue(tree), res);
            Console.WriteLine(tree);
		}

		[SUnitTestCase]
		public static void TestInOrder()
		{
			BinarySearchTree tree = new BinarySearchTree(5);

			tree.Insert(11);
			tree.Insert(94);
			tree.Insert(3);
			tree.Insert(82);

			CValue[] parameters = new CValue[] { _getBSTValue(tree) };
			CValue res = DynamicTest.InvokeFunction("getBSTInOrder", parameters, CTypes.String);
			DynamicTest.AssertEquals(new CString(tree.InOrder()), res);
		}

		[SUnitTestCase]
		public static void TestCount()
		{
			BinarySearchTree tree = new BinarySearchTree(5);

			tree.Insert(11);
			tree.Insert(94);
			tree.Insert(3);
			tree.Insert(82);

			CValue[] parameters = new CValue[] { _getBSTValue(tree) };
			CValue res = DynamicTest.InvokeFunction("getBSTCount", parameters, CTypes.Int);
			DynamicTest.AssertEquals(new CInt(tree.Count()), res);
		}

		private static CPointerType _getBSTType()
		{
			if (!CTypes.IsDeclaredType("node"))
			{
				CTypes.DeclareNewType("node");
				CTypes.DefineType("node", CTypes.Struct(new CType[] { CTypes.Pointer("node"), CTypes.Int, CTypes.Pointer("node") }));
				return CTypes.Pointer("node");
			}
			else
				return CTypes.Pointer(CTypes.GetDefinedType("node"));
		}

		private static CValue _getBSTValue(BinarySearchTree tree)
		{
			CPointerType ab = _getBSTType();

			if (tree == null)
				return new CPointer(ab, null);
			else
				return new CPointer(ab, new CStruct(ab.PointedType as CStructType, new CValue[] { _getBSTValue(tree.Left), new CInt(tree.Value), _getBSTValue(tree.Right) }));
		}
	}

	public class BinarySearchTree
	{
		public BinarySearchTree Left;
		public BinarySearchTree Right;
		public int Value = int.MinValue;

		public BinarySearchTree(int root)
		{
			Value = root;
		}

		public void Insert(int val)
		{
			if (val >= Value)
			{
				if (Right == null)			
					Right = new BinarySearchTree(val);
				else
					Right.Insert(val);
			}
			else
			{
				if (Left == null)			
					Left = new BinarySearchTree(val);
				else
					Left.Insert(val);
			}
		}
	
		public int Count()	
		{
			int count = 1;
		
			if (Left != null)
				count += Left.Count();
			if (Right != null)
				count += Right.Count();
			
			return count;
		}
	
		public string InOrder()
		{		
			StringBuilder sb = new StringBuilder();
		
			if (Left != null)
				sb.Append(Left.InOrder());
		
			sb.AppendFormat("{0},", Value.ToString());
		
			if (Right != null)
				sb.Append(Right.InOrder());
			
			return sb.ToString();
		}

        public override string ToString()
        {
            return InOrder();
        }
	}
}
